package com.cuz.daileetcode.bat100;

public class 跳跃游戏2 {
    public static void main(String[] args) {
        int[] ints = {2, 3, 1, 1, 4};
        System.out.println(lessStepNeedJump(ints));
    }
    public static int lessStepNeedJump(int[] arr) {
        if (arr == null || arr.length <= 1) {
            //有的人一出生就在罗马
            return 0;
        }
        int stepNeed = 1;
        //上一次最远到哪儿
        int preFastIndex = Math.max(1, arr[0]);
        //上一步到哪儿
        int endOfPreJump = preFastIndex;
        for (int i = 1; i < arr.length-1; i++) {
            //更新最远的位置
            preFastIndex = Math.max(i + arr[i], preFastIndex);
            //如果当前已经到了最远的位置
            if (i == endOfPreJump) {
                //那么我们花一步来到当前最远
                endOfPreJump = preFastIndex;
                stepNeed++;
            }
        }
        return stepNeed;
    }
}
